The invention relates to electronic communications and more particularly to packet-switched data networks.
In packet-switched networks, packets of digitized data are sent from a source to a destination, often in different routes depending upon capabilities and availabilities of different links between the source and the destination. Data are routed through links connecting nodes. Data can be sent across various links stemming from a node.
Unlike telephone networks where all traffic travels on circuits of fixed bandwidth where the sum of the bandwidth of all the circuits at any point does not exceed the speed of the link connecting network nodes, in packet networks it is often the case that the sum of the bandwidth of the traffic that wishes to cross a link between networking components exceeds the speed of the link. When this occurs there are more packets arriving at the node than can be transmitted, such a condition is referred to as overload or congestion. The packets that can not be transmitted immediately can be discarded or stored in a buffer for later transmission. Since there is a finite amount of storage space, if the overload condition persists eventually the buffer capacity of the node will be exhausted and all incoming packets will have to be discarded until the transmission of a packet frees some buffer space.
Packet networks are typically shared by multiple users and these users may have differing service requirements. The network may be able to selectively discard packets during overload to try to meet these different user requirements. The users are essentially anything that causes packets of data to be transmitted to a network such as humans, applications running on computers, network-attached hardware devices, or combinations of any of these. The term flow may be used interchangeably with user, although a user might have more than one flow.
Systems with FIFO scheduling/buffering mechanisms for selective packet discard typically involve discarding traffic based on its importance and how big the queue is when the packet arrives. In these mechanisms when the buffer is partially full low priority traffic is discarded, as the buffer becomes more full, traffic of higher priority is discarded. With such mechanisms it may be very difficult to “tune” the discard thresholds so that the system operates at high utilization and that all service requirements are met. In some cases it is impossible to achieve one without sacrificing the other.